package dfs;

import java.util.*;

/**
 * @author <a href="zhaoyingling12@163.com">Zhao Simon</a>
 * @description: https://leetcode.cn/problems/word-search/ 79 单词搜索
 * @date 2023/03/12
 **/
public class WordSearch {
    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'C', 'A', 'A'},
                {'A', 'A', 'A'},
                {'B', 'C', 'D'}
        };
        String word = "AAB";

        Solution solution = new Solution();
        System.out.println(solution.exist(board, word));

    }

   static class Solution {
        public boolean exist(char[][] board, String word) {
            if (board == null || board.length == 0) {
                return false;
            }

            char[] words = word.toCharArray();
            boolean[][] visited = new boolean[board.length][board[0].length];
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[0].length; j++) {
                    if (board[i][j] != words[0]) {
                        continue;
                    }
                    visited[i][j] = true;
                    boolean isExist = isExist(board, i, j, words, 1, visited);
                    if (isExist) {
                        return true;
                    }
                    visited[i][j] = false;
                }
            }
            return false;
        }

        private boolean isExist(char[][] board, int x, int y, char[] words, int index, boolean[][] visited) {
            // 说明前面的已经匹配完毕
            if (index >= words.length) {
                return true;
            }
            boolean up = false, down = false, left = false, right = false;

            // 上
            if (x - 1 >= 0 && !visited[x - 1][y] && board[x - 1][y] == words[index]) {
                visited[x - 1][y] = true;
                up = isExist(board, x - 1, y, words, ++index, visited);
                visited[x - 1][y] = false;
            }
            if (up) {
                return true;
            }

            // 下
            if (x + 1 < board.length && !visited[x + 1][y] && board[x + 1][y] == words[index]) {
                visited[x + 1][y] = true;
                down = isExist(board, x + 1, y, words, ++index, visited);
                visited[x + 1][y] = false;
            }
            if (down) {
                return true;
            }
            // 左
            if (y - 1 >= 0 && !visited[x][y - 1] && board[x][y - 1] == words[index]) {
                visited[x][y - 1] = true;
                left = isExist(board, x, y - 1, words, ++index, visited);
                visited[x][y - 1] = false;
            }
            if (left) {
                return true;
            }
            // 右
            if (y + 1 < board[0].length && !visited[x][y + 1] && board[x][y + 1] == words[index]) {
                visited[x][y + 1] = true;
                right = isExist(board, x, y + 1, words, ++index, visited);
                visited[x][y + 1] = false;
            }
            if (right) {
                return true;
            }
            return false;
        }
    }
}



